package dp.maxsum;

public class leetcode918环形子数组的最大和 {
    // S = S1 + S2，不跨环求最大，跨环求最小
    // 未优化
    public int maxSubarraySumCircular(int[] nums) {
        int length = nums.length;
        int[] maxDp = new int[length];
        int[] minDp = new int[length];
        maxDp[0] = nums[0];
        minDp[0] = nums[0];
        int max = nums[0];
        int min = nums[0];
        int sum = nums[0];
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                maxDp[i] = Integer.max(nums[i], maxDp[j] + nums[i]);
                minDp[i] = Integer.min(nums[i], minDp[j] + nums[i]);
            }
            sum += nums[i];
            max = Integer.max(max, maxDp[i]);
            min = Integer.min(min, minDp[i]);
        }
        // 剔除全为负数的情况
        if (max < 0) {
            return max;
        }
        return Integer.max(max, sum - min);
    }

    // 优化版本
    public int maxSubarraySumCircular1(int[] nums) {
        int length = nums.length;
        int curMax, curMin, max, min ,sum;
        curMax = curMin = max = min = sum = nums[0];
        for (int i = 1; i < length; i++) {
            curMax = Integer.max(curMax + nums[i], nums[i]);
            curMin = Integer.min(curMin + nums[i], nums[i]);
            max = Integer.max(curMax, max);
            min = Integer.min(curMin, min);
            sum += nums[i];
        }
        if (max < 0) {
            return max;
        }
        return Integer.max(max, sum - min);
    }
}
